package leecode

import (
	"container/list"
	"math/rand"
)

type RandomizedSet struct {
	numMap map[int]int
	result *list.List
	ValMap map[int]*list.Element
}

func Constructor1() RandomizedSet {
	result := list.New()
	numMap := make(map[int]int)
	valMap := make(map[int]*list.Element)
	return RandomizedSet{
		numMap: numMap,
		result: result,
		ValMap: valMap,
	}
}

func (this *RandomizedSet) Insert(val int) bool {
	_, ok := this.numMap[val]
	if ok {
		return false
	}
	element := this.result.PushBack(val)
	this.ValMap[val] = element
	this.numMap[val] = this.numMap[val] + 1
	return true
}

func (this *RandomizedSet) Remove(val int) bool {
	_, ok := this.numMap[val]
	if !ok {
		return false
	}
	element := this.ValMap[val]
	this.result.Remove(element)
	delete(this.numMap, val)
	return true
}

func (this *RandomizedSet) GetRandom() int {
	nums := make([]int, this.result.Len())
	index := 0
	for i := this.result.Front(); i != nil; i = i.Next() {
		nums[index] = i.Value.(int)
		index++
	}
	return nums[rand.Intn(len(nums))]
}
